package com.lihui.exercises;

import java.util.Stack;

/**
 * 功能描述
 *
 * @author wileda
 * @date 2022/10/18  15:44
 */
public class Exe_Stack {
    //有效的括号
    public boolean isValid(String s) {
        if(s == null || s.equals("")){
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.peek();
                if (top == '(' && ch == ')' || top == '[' && ch == ']' || top == '{' && ch == '}') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if(!stack.isEmpty()){
            return false;
        }
        return true;
    }

// 栈的压入 弹出序列
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA == null || pushA.length == 0){
            return false;
        }
         Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while(j < popA.length && !stack.isEmpty() && stack.peek() == popA[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }

    // 逆波兰表达式

    public int evalRPN(String[] tokens) {
        if(tokens == null || tokens.equals("")){
            return -1;
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String str = tokens[i];
            boolean b1 = isOperator(str);
            if (b1){
                int b = stack.pop();
                int a = stack.pop();
                switch (str){
                    case "+":
                        stack.push(a + b);
                        break;
                    case"-":
                        stack.push(a - b);
                        break;
                    case"*":
                        stack.push(a * b);
                        break;
                    case"/":
                        stack.push(a / b);
                        break;
                }
            }else {
                stack.push(Integer.valueOf(str));
            }
        }
        return stack.pop();
    }

    private boolean isOperator(String str) {
        if (str == null || str.equals("")){
            return false;
        }
        if(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")){
            return true;
        }
        return false;
    }

  //最小栈
  class MinStack {
      Stack<Integer> stack;
      Stack<Integer> minStack;

      public MinStack() {
          stack = new Stack<>();
          minStack = new Stack<>();
      }

      public void push(int val) {
          stack.push(val);
          if(minStack.isEmpty() || val <= minStack.peek()){
              minStack.push(val);
          }
      }

      public void pop() {
          if(minStack.isEmpty()){
              return;
          }
          int n = stack.pop();
          if(!minStack.isEmpty() && n == minStack.peek() ){
              minStack.pop();
          }
      }

      public int top() {
          if(stack.isEmpty()){
              return -1;
          }
          return stack.peek();
      }

      public int getMin() {
          if(minStack.isEmpty()){
              return -1;
          }
          return minStack.peek();
      }
  }
}
